package com.zjsru.leetcode75.level1;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @Author: cookLee
 * @Date: 2023-11-05
 * 小行星碰撞
 */
public class AsteroidCollision {

    /**
     * 主
     * \
     * 输入：asteroids = [5,10,-5]
     * 输出：[5,10]
     * 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
     * \
     * 输入：asteroids = [8,-8]
     * 输出：[]
     * 解释：8 和 -8 碰撞后，两者都发生爆炸。
     * \
     * 输入：asteroids = [10,2,-5]
     * 输出：[10]
     * 解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        AsteroidCollision asteroidCollision = new AsteroidCollision();
        int[] asteroids = new int[]{5, 10, -5};
        System.out.println(Arrays.toString(asteroidCollision.asteroidCollision(asteroids)));
    }

    /**
     * 小行星碰撞:栈模拟
     *
     * @param asteroids 小行星
     * @return {@link int[]}
     */
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        //入栈
        for (int asteroid : asteroids) {
            //设定遍历判断小行星是否还存在
            boolean flag = true;
            //此时栈中拿出的元素都是正数 即是同一方向的元素
            while (flag && asteroid < 0 && !stack.isEmpty() && stack.peek() > 0) {
                Integer exsitAsteroid = stack.peek();
                //表示后续操作下该行星一定不会存在
                flag = exsitAsteroid < -asteroid;
                //栈中元素 不同方向且大小处于劣势
                if (exsitAsteroid <= -asteroid) {
                    stack.pop();
                }
            }
            //false即说明行星和栈中的是反方向并且已经被消灭
            if (flag) {
                stack.push(asteroid);
            }
        }
        int[] ans = new int[stack.size()];
        //出栈后 长度实时变化，考虑从后遍历归入 保证数据完整
        for (int i = stack.size() - 1; i >= 0; i--) {
            ans[i] = stack.pop();
        }
        return ans;
    }

}
